package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description: 35. 搜索插入位置 {@literal https://leetcode-cn.com/problems/search-insert-position/}
 * @date: 2020/11/26 0026 17:08
 */
public class J0035_E_SearchInsert {
    /*
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    你可以假设数组中无重复元素。
     */

    /**
     * 找到大于等于的位置
     */
    public static int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int l = 0;
        int r = len - 1;
        //保证left <= target
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            }
            //当前位置比目标小：说明还没到到指定的位置，把左边移动到中间位置
            if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        //2
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 5));
        //1
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 2));
        //4
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 7));
        //0
        System.out.println(searchInsert(new int[]{1, 3, 5,}, 0));

    }
}
